package sit.engreal.leetcode.problems200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/triangle/">120. 三角形最小路径和</a>
 */
public class LeetCode120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] cost = new int[n + 2];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[1] = 0;
        for (final List<Integer> floor : triangle) {
            int leftUp = cost[0];
            for (int i = 0; i < floor.size(); i++) {
                final int up = cost[i + 1];
                cost[i + 1] = Math.min(leftUp, up) + floor.get(i);
                leftUp = up;
            }
        }
        int v = cost[1];
        for (int i = 2; i < cost.length - 1; i++) {
            v = Math.min(v, cost[i]);
        }
        return v;
    }

    public static void main(String[] args) {
        final LeetCode120 demo = new LeetCode120();
        {
            final List<List<Integer>> triangle = array2list(new int[][]{
                    {2},
                    {3, 4},
                    {6, 5, 7},
                    {4, 1, 8, 3}
            });
            System.out.println(demo.minimumTotal(triangle));
        }
        {
            final List<List<Integer>> triangle = array2list(new int[][]{
                    {2}
            });
            System.out.println(demo.minimumTotal(triangle));
        }
    }

    public static List<List<Integer>> array2list(int[][] array) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int[] values : array) {
            final ArrayList<Integer> list = new ArrayList<>(values.length);
            for (int i : values) {
                list.add(i);
            }
            lists.add(list);
        }
        return lists;
    }
}
